package offer;

public class offerII_0017 {
    public static void main(String[] args) {
        minWindow("ADOBECODEBANC", "ABC");
    }
    public static String minWindow(String s, String t) {
        int lens=s.length();
        int lent=t.length();
        int [] num=new int[52];
        if(lens<lent) return "";
        int min_len=lens+1;
        for(int i=0;i<lent;++i){
            if(t.charAt(i)<='Z'&&t.charAt(i)>='A'){
                num[t.charAt(i)-'A']+=1;
            }
            else{
                num[t.charAt(i)-'a'+26]+=1;
            }
        }
        int left=0;
        int right=1;
        while(right<lens&&!notzero(s.charAt(left),num)){
            left++;
            right++;
        }
        sub1(s.charAt(left),num);
        String result="";
        while(right<=lens){
            if(empty(num)){
                while(left<right&&lowzero(s.charAt(left),num)){
                    add1(s.charAt(left),num);
                    left++;
                }
                if(min_len>right-left){
                    min_len=right-left;
                    result=s.substring(left,right);
                }
                while(left<right&&!zero(s.charAt(left),num)){
                    add1(s.charAt(left),num);
                    left++;
                }
                add1(s.charAt(left),num);
                left++;
                while(left<right&&lowzero(s.charAt(left),num)){
                    add1(s.charAt(left),num);
                    left++;
                }
            }
            else{
                if(right==lens) break;
                sub1(s.charAt(right),num);
                right++;
            }
        }

        return result;
    }
    public static void add1(char a,int[] num){
        if(a<='Z'&&a>='A'){
            num[a-'A']+=1;
        }
        else{
            num[a-'a'+26]+=1;
        }
    }
    public static void sub1(char a,int[] num){
        if(a<='Z'&& a>='A'){
            num[a-'A']-=1;
        }
        else{
            num[a-'a'+26]-=1;
        }
    }
    public static boolean empty(int[] num){
        for(int i=0;i<52;++i){
            if(num[i]>0) return false;
        }
        return true;
    }
    public static boolean lowzero(char a,int[] num){
        if(a<='Z'&& a>='A'){
            return num[a-'A']<0;
        }
        else{
            return num[a-'a'+26]<0;
        }
    }
    public static boolean notzero(char a,int[] num){
        if(a<='Z'&& a>='A'){
            return num[a-'A']>0;
        }
        else{
            return num[a-'a'+26]>0;
        }
    }
    public static boolean zero(char a,int[] num){
        if(a<='Z'&& a>='A'){
            return num[a-'A']==0;
        }
        else{
            return num[a-'a'+26]==0;
        }
    }
}
